

//随机抽取一个数作为基准位  比这个数大的放在右边，比这个数小的放在左边  然后重复递归
// O(n*lgn)
function quickSort(arr){
    if(arr.length<2){ //要排序的个数小于2 ，直接返回
        return arr 
    }
    let flag = arr[0]
    let left = []
    let right = []
    for(let i=1;i<arr.length-1;i++){
        
        if(a[i] > flag){
            right.push(arr[i])
        }else{
            left.push(arr[i])
        }
    }
    return quickSort(left).concat(flag,quickSort(right))
}


//原地快排(没有用多余的空间) 有点难理解
//   i->           <-j
// e [a,b,c,d,e,f,g,h]
//i找比e大的，j找比e小的
//i和j的值交换一下位置
//最后i和j遇见
function quick(arr,start,end){
    //双指针
    let init = start
    let flag = arr[init]
    start++//跳过第一个数，因为第一个数是标志位
    while(start <= end){
        while(arr[start]>flag){
            start++
        }
        while(arr[end]<flag){
            end--
        }
        if(start<end){
            [arr[start],arr[end]] =[arr[end],arr[start]]
            start++
            end--
        }
    }
    [arr[init],arr[start-1]] =[arr[start-1],arr[init]]//把起始位和标记为换位置
    return start
}
function quickSortStand(arr,start,end){
    if(start<end){
        let index = quick(arr,start,end)
        quickSortStand(arr,start,index-1)
        quickSortStand(arr,index,end)
    } 
    return arr
}

